#include <iostream>
#include <ctime>
#include <stack>
using namespace std;
const int maxsize=100;
int a[maxsize];
int n;
void print()
{
    for (int i = 0; i < n; ++i) {
         cout<<a[i]<<" ";
    }
    cout<<endl;
}
int Partion(int left,int right)
{
    int temp=a[left];
    int i=left,j=right;
    while(i<j)
    {
        while(a[j]>=temp&&i<j) j--;
        //判断是不是相遇退出循环的
        if(i<j)
        {
            a[i++]=a[j];
        }
        while(a[i]<=temp&&i<j) i++;
        if(i<j)
        {
            a[j--]=a[i];
        }
    }
    a[i]=temp;
    return i;
}
void QuickSort(int left,int right)
{
   stack<int> s;
   if(left<right)
   {
       s.push(right);
       s.push(left);
   }

   while(!s.empty())
   {
       int l=s.top();
       s.pop();
       int r=s.top();
       s.pop();
       int mid=Partion(l,r);
       if(l<mid-1)
       {
           s.push(mid-1);
           s.push(l);
       }
       if(mid+1<r)
       {
           s.push(r);
           s.push(mid+1);
       }
   }
}
void quicksort(int left,int right)
{
    if(left>=right)
        return ;
    int i=Partion(left,right);
    quicksort(left,i-1);
    quicksort(i+1,right);
}
int main() {
    cin>>n;
    srand(time(0));
    for (int i = 0; i <n ; ++i) {
        a[i]=rand()%100+1;
    }
    print();
    QuickSort(0,n-1);
    print();


    return 0;
}
